/**
 * 需求: 求大于一个数的最小二次幂
 * <hr>
 * 算法: 二进数的位对应的就是二的次幂
 * <br>
 * 时间复杂度: O(1)
 * <br>
 * 空间复杂度: O(1)
 * <p>
 * 知识点:
 * <br>
 * 1. 位运算-左移: 符号位也移动, 右侧补 0, 如果符号位不变, 相当有给数乘以二                                  <br>
 * 2. 位运算-右移:                                                                                   <br>
 * 正数, 左侧补 0, 相当于给数除以二并向小取整                                                             <br>
 * 负数(补码), 左侧补 1, 相当于给数除以二并向小取整                                                        <br>
 * 3. 位运算-无符号右移: 最高位补零                                                                      <br>
 * 4. 二进数的位对应的就是二的次幂
 * <p>
 * 2次方是 squared or 2nd power
 * 3次方是 cubic or 3rd power
 * 4次方是 4th power
 * 5次方是 5th power
 */
class LeastSquared {

    public static void main(String[] args) {
        System.out.println(leastSquared(-123));
        System.out.println(tableSizeFor(-123));
    }


    /**
     * 把数减一后, 转成二进制, 获取最高位的1对应的十进制数, 乘以2
     * <p>
     * 时间复杂度: O(1)
     * <br>
     * 空间复杂度: O(1)
     */
    public static int leastSquared(Integer capacity) {
        // 小于 0 的数直接返回一个指定值
        // if (capacity < 0) {
        //     return 1;
        // }

        // 获取一个数的二进制最高位
        int i = capacity - 1;

        // 带符号右移, 如果是负数, 左侧补 1, 相当于给负数除以二并向小取整
        // 将最高位的 1 右移 1 位后, 在与其或运算, 则最高位及最高位的后一位都是 1 了
        // System.out.println(i >> 1);
        i |= (i >> 1);
        i |= (i >> 2);
        i |= (i >> 4);
        i |= (i >> 8);
        i |= (i >> 16);

        // 最高的位是 1 对应的数
        // System.out.println(i >>> 1);
        i = i - (i >>> 1);

        // 乘以二
        i <<= 1;
        // 和 JDK API 做个比较
        if (i != valid(capacity) << 1) {
            throw new ArithmeticException();
        }
        return i;
    }

    public static int valid(Integer capacity) {
        // 获取一个数的二进制最高位
        return Integer.highestOneBit(capacity - 1);
    }


    /**
     * 先把数转成二进制，然后把真值减一后的最高一位 1 之后所有位的数变成 1，最后 +1
     * <br>
     * 时间复杂度: O(1)
     * <br>
     * 空间复杂度: O(1)
     * <p>
     * 步骤:                                                      <br>
     * 13          : 十进制转二进制                                 <br>
     * 0000 1101   : 转为二进制                                    <br>
     * 0000 1100   : 减一, 防止本身就是二的次幂加一后扩大              <br>
     * 0000 1111   : 将真值的部分全部转为一                          <br>
     * 0001 0000   : 加一                                         <br>
     * 16          : 二进制转为十进制                               <br>
     * <p>
     * 这段算法的代码拷贝自 HashMap#tableSizeFor(int)
     */
    public static int tableSizeFor(int capacity) {
        // int 型最大的正二的次幂
        // 0000 0000 0000 0000  0000 0000 0000 0001 <<30  0100 0000 0000 0000  0000 0000 0000 0000
        int MAXIMUM_CAPACITY = 1 << 30;

        // 减一的目的是防止传入的就是 2 的 n 次幂
        int n = capacity - 1;

        // n = 129   n-1 = 128
        // 0000 0000 0000 0000  0000 0000 1000 0000 >>>1  0000 0000 0000 0000  0000 0000 0100 0000
        // 0000 0000 0000 0000  0000 0000 1000 0000  n
        // 0000 0000 0000 0000  0000 0000 0100 0000  n >>> 1
        // 0000 0000 0000 0000  0000 0000 1100 0000  n |= n >>> 1
        n |= n >>> 1;
        // 0000 0000 0000 0000  0000 0000 1100 0000
        // 0000 0000 0000 0000  0000 0000 0011 0000
        // 0000 0000 0000 0000  0000 0000 1111 0000
        n |= n >>> 2;
        // 0000 0000 0000 0000  0000 0000 1111 0000
        // 0000 0000 0000 0000  0000 0000 0000 1111
        // 0000 0000 0000 0000  0000 0000 1111 1111
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;

        // 比负数大的最小二次幂为 0, HashMap 负数初始化为 1 了
        // return (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }
}